Illustrated herein are embodiments of a method and system relating to the validation and analysis of JDF workflows using colored Petri nets. The embodiments disclosed herein find particular application in conjunction with workflows relating to printing jobs and will be described with particular reference thereto. However, it is to be appreciated that these embodiments are also amenable to other like applications.
Generally, a workflow represents a flow of work. In a business corporation, for example, suppose that one of the members of the corporation is going to purchase an article. First, the person prepares a purchase slip and then brings the purchase slip to the superior. The superior checks the purchase slip, stamps the approval, and sends the purchase slip to the accounting department. Based on the purchase slip, the accounting department orders the article. As seen in the above-mentioned workflow, the purchase slip flows from the person to the superior, and from the superior to the accounting department, thus advancing the workflow. Therefore, a workflow can be considered a sequence of tasks. A task can be further divided into sub-tasks. Tasks can be performed by persons as in the foregoing example, and can automatically be performed by computers as, for example, in a printing job.
Workflow-based businesses rely heavily on their ability to effectively compete in and control existing and emerging workflows. Given the heterogeneity of the space, integration of these heterogeneous distributed systems is a considerable challenge and is fast becoming a critical factor of success in business. In addition to the multiplicity of systems, customers are demanding customization and flexibility for their workflows. As a result, automation of the integration and deployment of workflows today means considerable competitive advantage. Effective modeling is a key part of an overall workflow automation strategy.
Current workflow modeling technologies and tools enable clever visualization and some analysis capability. However, their effectiveness relies heavily upon the idiosyncratic knowledge and expertise of the person doing the modeling. That is, it is a highly manual and cumbersome effort and yields results only as good as the intuition and skill of the particular modeler.
JDF (Job Definition Format) is an industry standard designed to simplify information exchange between different applications and systems in and around the graphic arts industry. JDF is published by the International Cooperation for the Integration of Processes in Prepress, Press and Postpress Organization (CIP4) and specifies the information required to complete a customer intended print job. It enables the integration of commercial and planning applications into the technical workflow. JDF is a comprehensive XML-based file format and proposed industry standard for end-to-end job ticket specifications combined with a message description standard and message interchange protocol.
Conceptually, JDF has three main functions. First, it provides a single common language that supports the lifecycle of a print job. Thus, JDF is often referred to as a “Job Ticket” language. The second function is to provide a command and control language for devices on the shop floor. This aspect of JDF is called the Job Messaging Format (JMF). JMF allows the controlling workflow system or MIS in a process-automated environment to tell devices to start and stop jobs, reorder the queue, etc. Finally, there is inherent in JDF a flexible methodology for constructing workflows and providing the command, control, and configuration of plant automation and job production. There is a fourth main function of automating the handshake, which is accomplished with the new device capabilities functionality.
Generally, the information in JDF is organized into nodes in a hierarchical tree of processes and resources that each process produces and consumes. An XML-based JDF job describes the status of processes and resources at a particular instance. An MIS (Management Information System) is responsible for estimating, tracking, controlling and monitoring the entire production workflow. There are MIS vendors (such as EFI, Hiflex, iWay to name a few) that have already offered MIS products with varying capabilities to analyze and estimate the JDF workflow. But these existing analysis and estimation capabilities are very limited in terms of verifying both syntactic and semantic correctness of JDF workflow, and also lacking a simulation-based estimation on JDF workflow cost and performance.
JDF allows XML-based description of all the processes needed to complete a print product, from job submission through prepress, press and post press. Each process is defined in terms of the consumed input resources and produced output resources. Resources produced by one process might be required by other processes, and processes are interconnected in a chain of processes to form a complete workflow. Processes may share resources and be interconnected in sequential, parallel, overlapping and iteration fashion. Because of the complexity of the workflows that could result within a JDF instance it becomes difficult to manually analyze the validity of the workflow and perform predictive assessments for various performances and cost metrics to provide crucial business process management capabilities for the print shop. Currently most of the tools use a discrete event simulation package to asses the JDF-based workflow, but do not provide features to verify the correctness of JDF-based workflows.
One graphical approach which has been developed for modeling and simulating systems exhibiting concurrency and asynchronicity is that of Petri nets. One reason Petri net representations are used is that they are also analyzable. A good discussion of the history and general principles of Petri nets is contained in, for example, T. Murata, “Petri Nets: Properties, Analysis and Applications,” Proceedings of the IEEE, Vol. 77, No. 4, April 1989 (New York) at 541-580, and K. Jensen, “An Introduction to the Theoretical Aspects of Coloured Petri Nets,” in J. W. de Bakker, W. P. de Roever, G. Rozenberg (eds), “A Decade of Concurrency, Lecture Notes in Computer Science,” Vol. 803, Springer-Verlag 1994, at 230-272, both of which are hereby incorporated by reference.
Colored Petri nets (or CPNs) involve a formal modeling language that has Petri net based formal analysis with detailed and concise description of the model in programming languages. It is a graphical oriented language for design, specification, simulation and verification of systems. CPNs are, in particular, well-suited for systems that consist of a number of processes which communicate and synchronize. Typical examples of application areas are communication protocols, distributed systems, automated production systems, work flow analysis and VLSI (Very Large-Scale Integration) chips. A model could be analyzed with a reachability graph generated of the various available states from which various behavioral properties like deadlocks, livelocks, and boundedness of the model can be derived. Thus, for example, colored Petri nets have been used for controlling a large class of flexible manufacturing systems (FMS), as described in J. Ezpeleta and J. Colom, “Automatic Synthesis of Colored Petri Nets for the Control of FMS,” IEEE Transactions on Robotics and Automation, Vol. 13, No. 3, June 1997, which is hereby incorporated by reference.
Some have used an intermediate process calculus whereby the language level constructs of embedded systems have been mapped to Petri nets for analyzing the concurrency behavior. Others have synthesized colored Petri nets by generating process plans and the manufacturing system layout for formal modeling and analysis of flexible manufacturing systems. Yet others have applied a version of Petri nets for a behavioral specification of CORBA (Common Object Request Broker Architecture) in IDL (Interface Definition Language). In addition Petri nets have been applied to model a wide variety of applications like VLSI designs, control systems, software engineering, and mechanical systems. Some of the current workflow languages are based on underlying process calculus. Microsoft's XLANG is based on pi-calculus. For instance, IBM's WSFL (Web Service Flow Language) is based on Petri net semantics.
U.S. patent application Ser. No. 10/836,298 filed Apr. 30, 2004, entitled “WORKFLOW AUTO GENERATION FROM USER CONSTRAINTS AND HIERARCHICAL DEPENDENCE GRAPHS FOR WORKFLOWS,” by Tong Sun, et al., and hereby incorporated by reference for all it discloses, proposes a Hierarchical Dependence Graph for formal analysis of JDF workflows by using an extended DAG (directed acyclic graph). Based upon the graphic theory of DAG, this method allows a formal JDF workflow analysis on identifying the missing resources, the dangling process nodes in JDF and possible cyclic deadlock loop.
Thus, there is a need for an improved method and system for formal verification and analysis of a JDF-based workflow prior to execution semantic analysis in terms of all possible resource and process states, reachability, boundedness and liveliness analysis.